/*
 * Heuristic.cpp
 *
 *  Created on: 28/08/2014
 *      Author: santosma
 */

#include "Heuristic.h"
#include <stdio.h>

bool fabiosRule(int* vec, int n){
	for(int i = 0; i < n; i++) if(vec[i] >= 2) return true;
	return false;
}

int fabioschoose(int* vec, int n){
	int dgmax = 0;
	int dgi = -1;
	int dg;
	for(int i = 0; i < n; i++){
		dg = vec[i];
		if(dg > dgmax){
			dgmax = dg;
			dgi = i;
		}
	}
	return dgi;
}

double Heuristic::UB_FabioHeur(Graph* g){
	long n = g->numV();
	long v, n1, n2;
	BitVector* whites = new BitVector(n);
	BitVector* grays = new BitVector(n);
	BitVector* blacks = new BitVector(n);
	BitVector* ng, *nu;
	int dg[n];
	whites->setAll();
	blacks->unsetAll();
	grays->unsetAll();
	for(int i = 0; i < n; i++) dg[i] = g->degree(i);
	while(fabiosRule(dg, n)){
		v = fabioschoose(dg, n);
		dg[v] = 0;
		whites->unset(v);
		grays->unset(v);
		blacks->set(v);
		ng = g->neig(v);
		n1 = ng->firstOneAfter(0);
		while(n1 < n){
			if(whites->isSet(n1)){
				grays->set(n1);
				whites->unset(n1);
				nu = g->neig(n1);
				n2 = nu->firstOneAfter(0);
				while(n2 < n){
					dg[n2]--;
					n2++;
					n2 = nu->firstOneAfter(n2);
				}
			}
			n1++;
			n1 = ng->firstOneAfter(n1);
		}
	}
	return 2*blacks->count() + grays->count();
}

double Heuristic::UB_SamuelHeur(Graph* g){
	long n = g->numV();
	long v, n1, n2, it = 0;
	BitVector* visited = new BitVector(n);
	BitVector* ng, *nu;
	int dg[n];
	visited->setAll();
	for(int i = 0; i < n; i++) dg[i] = g->degree(i);
	while(fabiosRule(dg, n)){
		it++;
		v = fabioschoose(dg, n);
		dg[v] = 0;
		visited->unset(v);
		ng = g->neig(v);
		n1 = ng->firstOneAfter(0);
		while(n1 < n){
			if(visited->isSet(n1)){
				visited->unset(n1);
				nu = g->neig(n1);
				dg[n1] = 0;
				n2 = nu->firstOneAfter(0);
				while(n2 < n){
					dg[n2]--;
					n2++;
					n2 = nu->firstOneAfter(n2);
				}
			}
			n1++;
			n1 = ng->firstOneAfter(n1);
		}
	}
	return 2*it + visited->count();
}

double Heuristic::LB_degree(Graph* g){
	double maxdg = 0;
	double dg;
	for(int i = 0; i < g->numV(); i++){
		dg = g->degree(i);
		maxdg = (maxdg < dg)? dg: maxdg;
	}
	return ((double)(2*g->numV()))/(maxdg+1.0);
}

double Heuristic::UB_FabioHeur(Graph* g, BitVector* nV){
	long n = g->numV();
	long v, n1, n2;
	BitVector* whites = new BitVector(n);
	BitVector* grays = new BitVector(n);
	BitVector* blacks = new BitVector(n);
	BitVector* ng, *nu;
	int dg[n];
	whites->setAll();
	whites->dot(nV);
	blacks->unsetAll();
	grays->unsetAll();
	for(int i = 0; i < n; i++) dg[i] = g->degreeOn(i, nV);
	while(fabiosRule(dg, n)){
		v = fabioschoose(dg, n);
		dg[v] = 0;
		whites->unset(v);
		grays->unset(v);
		blacks->set(v);
		ng = g->neig(v);
		n1 = ng->firstOneAfter(0);
		while(n1 < n){
			if(whites->isSet(n1)){
				grays->set(n1);
				whites->unset(n1);
				nu = g->neig(n1);
				n2 = nu->firstOneAfter(0);
				while(n2 < n){
					dg[n2]--;
					n2++;
					n2 = nu->firstOneAfter(n2);
				}
			}
			n1++;
			n1 = ng->firstOneAfter(n1);
		}
	}
	return 2*blacks->count() + grays->count();
}

double Heuristic::UB_SamuelHeur(Graph* g, BitVector* nV){
	long n = g->numV();
	long v, n1, n2, it = 0;
	BitVector* visited = new BitVector(n);
	BitVector* ng, *nu;
	int dg[n];
	visited->setAll();
	for(int i = 0; i < n; i++) dg[i] = g->degreeOn(i, nV);
	while(fabiosRule(dg, n)){
		it++;
		v = fabioschoose(dg, n);
		dg[v] = 0;
		visited->unset(v);
		ng = g->neig(v);
		n1 = ng->firstOneAfter(0);
		while(n1 < n){
			if(visited->isSet(n1)){
				visited->unset(n1);
				nu = g->neig(n1);
				dg[n1] = 0;
				n2 = nu->firstOneAfter(0);
				while(n2 < n){
					dg[n2]--;
					n2++;
					n2 = nu->firstOneAfter(n2);
				}
			}
			n1++;
			n1 = ng->firstOneAfter(n1);
		}
	}
	return 2*it + visited->count();
}

double Heuristic::LB_degree(Graph* g, BitVector* nV){
	double maxdg = 0;
	double dg;
	for(int i = 0; i < g->numV(); i++){
		dg = g->degreeOn(i, nV);
		maxdg = (maxdg < dg)? dg: maxdg;
	}
	return ((double)(2*g->numV()))/(maxdg+1.0);
}
